__author__ = 'st316'
'''
Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

constant space :self space
'''


class Solution:
    # @param A, a list of integers
    # @return an integer
    def firstMissingPositive(self, A):
        n = len(A)
        i = 0
        while i < n:
            tmp = A[i] - 1
            if A[i] > 0 and A[i] - 1 < n and A[i] != i + 1 and A[i] != A[tmp]:
                A[i], A[tmp] = A[tmp], A[i]
            else:
                i += 1
        for i in xrange(n):
            if A[i] != i + 1:
                return i + 1
        return n + 1


if __name__ == '__main__':
    s = Solution()
    print s.firstMissingPositive([])